
#include <iostream>
#include <assert.h>
using namespace std;

void Swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}


void InsertSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (a[end] > tmp)
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}

void _MergeSort(int* a, int left, int right, int* tmp)
{
	if (left >= right)
		return;

	int mid = (left + right) / 2;
	_MergeSort(a, left, mid, tmp);
	_MergeSort(a, mid + 1, right, tmp);

	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	int index = begin1;

	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
			tmp[index++] = a[begin1++];
		else
			tmp[index++] = a[begin2++];
	}

	while (begin1 <= end1)
		tmp[index++] = a[begin1++];

	while (begin2 <= end2)
		tmp[index++] = a[begin2++];

	memcpy(a + left, tmp + left, sizeof(int) * (end2 - left + 1));
}



void MergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	assert(tmp);
	
	_MergeSort(a, 0, n - 1, tmp);
	free(tmp);
}



void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	assert(tmp);
	int gap = 1;

	while (gap < n)
	{
		for (int i = 0; i < n; i += 2 * gap)
		{
			int begin1 = i, end1 = i +  gap - 1;
			int begin2 = i + gap,  end2 = i + 2 * gap - 1;
			int index = i;
			
			if (end1 >= n || begin2 >= n)
				break;

			if (end2 >= n)
				end2 = n - 1;


			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] < a[begin2])
				{
					tmp[index++] = a[begin1++];
				}
				else
				{
					tmp[index++] = a[begin2++];
				}
			}

			while (begin1 <= end1)
				tmp[index++] = a[begin1++];

			while (begin2 <= end2)
				tmp[index++] = a[begin2++];

			memcpy(a + i, tmp + i, (end2 - i +1) * sizeof(int));
		}
		
		gap *= 2;
	}
}






int main()
{
	int arr[1000] = { 0 };
	int n = 1000;
	for (int i = 0; i < 1000; i++)
	{
		arr[i] = rand() % 10000;
	}

	//InsertSort(arr, n);
	//MergeSort(arr, n);

	MergeSortNonR(arr, n);

	for (int i = 0; i < n; i++)
	{
		printf("%d\n", arr[i]);
	}
	
	return 0;
}







//struct ListNode
//{
//    int val;
//    struct ListNode* next;
//};
//
//
//
//
//
//struct ListNode* getMidNode(struct ListNode* cur)
//{
//    struct ListNode* fast = cur, * slow = cur;
//    while (fast && fast->next)
//    {
//        fast = fast->next->next;
//        slow = slow->next;
//    }
//
//    return slow;
//}
//
//struct ListNode* Reverse(struct ListNode* head)
//{
//    struct ListNode* cur = head, * pre = nullptr;
//    while (cur)
//    {
//        struct ListNode* save = cur->next;
//        cur->next = pre;
//
//        pre = cur;
//        cur = save;
//    }
//
//    return pre;
//}
//
//bool isPalindrome(struct ListNode* head)
//{
//    struct ListNode* mid = getMidNode(head);
//    struct ListNode* rHead = Reverse(mid);
//
//    while (head && rHead)
//    {
//        if (head->val != rHead->val)
//            return false;
//
//        head = head->next;
//        rHead = rHead->next;
//    }
//
//    return true;
//}
//
//
//
//int main()
//{
//    struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));
//    head->val = 1;
//    head->next = nullptr;
//    
//    cout << isPalindrome(head) << endl;
//
//    return 0;
//}
//
//












